The Chien search is the algorithm to find the roots of an error locator polynomial over a field by substituting every element of the field. A serial Chien search circuit searches the roots by substituting a single element per clock cycle. In order to speed up the searching time, a parallel structure of the Chien search is required. However, its parallelism increases the area of the circuit.
In order to make our embodiment clear, we divide a Chien search circuit into two function blocks: root shift block and substitution block. Root shift block of p-parallel Chien search transforms the current polynomial which roots are, for instance, {β1, β2} into another one which roots are {αp×β1, αp×β2}. Substitution block of p-parallel Chien search substitutes α0, α1, . . . , and αp-1 into a shifted polynomial which is an output from root shift block. When the parallel factor p increases, substitution block needs an additional circuit to substitute another field element, while root shift block does not need an additional circuit but requires only replacement of the shift factor. Therefore, as the parallel factor p increases, so the area of substitution block increases, while increase of the area of root shift block is much less than that of substitution block.